#include <iostream>
#include <vector>
using namespace std;

int checkNum(int row) {
  int ret = 0;
  while (row) {
    ret += row % 10;
    row = row / 10;
  }
  return ret;
}

bool checkPosition(const int &rows,
                   const int &cols,
                   const int &row,
                   const int &col,
                   vector<vector<bool>> visited,
                   const int &threshold) {
  if (row >= 0 && row < rows &&
      col >= 0 && col < cols &&
      (checkNum(row) + checkNum(col) <= threshold) &&
      visited[row][col] == false) {
    return true;
  }
  return false;
}

int movingCountCore(const int &rows,
                    const int &cols,
                    const int &row,
                    const int &col,
                    vector<vector<bool>> &visited,
                    const int &threshold) {
  if (checkPosition(rows, cols, row, col, visited, threshold)) {
    visited[row][col] = true;
    return 1 + movingCountCore(rows, cols, row + 1, col, visited, threshold) +
               movingCountCore(rows, cols, row - 1, col, visited, threshold) +
               movingCountCore(rows, cols, row, col + 1, visited, threshold) +
               movingCountCore(rows, cols, row, col - 1, visited, threshold);
  }
  return 0;
}

int movingCount(const int& rows, const int &cols, const int &threshold) {
  vector<vector<bool>> visited;
  visited.resize(rows);
  for (auto i = 0; i < rows; ++i) {
    visited[i].assign(cols, 0);
  }
  return movingCountCore(rows, cols, 0, 0, visited, threshold);
}

int main() {
  cout << "(rows, cols, threshold, result, expected)" << endl;
  cout << "(10, 10, 5, " << movingCount(10, 10, 5) << ", 21)" << endl;
  cout << "(20, 20, 15, " << movingCount(20, 20, 15) << ", 359)" << endl;
  cout << "(1, 100, 10, " << movingCount(1, 100, 10) << ", 29)" << endl;
  return 0;
}
